/**
 * @file reviewBT.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2022-03-02
 *
 * @copyright Copyright (c) 2022
 *
 */

// 前中后层序，迭代
// 104.求最大深度：层序（层数）；递归（左右子树最大深度+1）；
// 111.求最小深度：层序（找到一个叶子节点即break）；递归（分情况讨论（左右都有孩子、无孩子、有一个孩子））
// 199.求每层最右边节点：层序（先右后左入队，队首元素即是）
// 637.层平均值、515.层最大值
// 429.N叉树层序遍历（循环遍历每个孩子呗）
// 116./117.填充下一个右侧节点的next域（116是完美二叉树，117是普通二叉树）
//          解决：层序通用（非最右边节点设置node->next=q.front())；递归（connectTwoNodes函数，适用于116）
// 226.翻转二叉树：层序（交换左右孩子）；递归（root->left=翻转左子树，root->right=翻转右子树，需要先保存反转后的结果，即后序）
// 100.相同的树：层序，每次出队比较一下（均是空节点、有一空、均非空）；递归也是一样
// 101.对称二叉树：递归（比较左右子树）；层序（每层首尾元素加入队列，判断（2空，1空，2非空），入队顺序）
// 572.判断某树是否为另一棵树的子树：递归（2树相同、左子树的子树、右子树的子树）
// 617.合并两个二叉树（值相加）：递归（考虑当前节点是否为空）；层序（一个队列，考虑孩子节点：若都有左孩子或右孩子，则双双入队；否则直接连相应节点）
// 222.完全二叉树的节点个数：普通二叉树（计数O(N)），满二叉树公式：2^h-1；那么完全二叉树则可以先求子树高，若左子树高=右子树高则用公式，否则计数
// 110.判断二叉树高度是否平衡：自底向上递归（左子树、右子树或二者高度差>1则不平衡，若平衡返回其高度）
// 404.左叶子之和：何为左叶子？只能通过其父节点来判断
//      node->left != null && node->left->left == null && node->left->right == null

// 回溯思想二叉树：
// 257.输出二叉树所有路径：path设成vector<int>回溯更方便
// 513.找树左下角的值（最底层最左边节点）：层序呀（记录每层第一个节点的值i==0）；递归（出现新深度时更新leftval，回溯）遍历顺序决定了同高度时只记录最左边的值
// 112.路径总和：是否有一条路径之和==target
//      要点：只需要找一条即可，backtracking需要返回值；需要遍历整个树，无需返回值
//      递归出口：叶子节点且diff==0，否则返回false呀，回溯时若是找到一条路径就true了
// 113.路径总和II：找到所有路径和==target（标准回溯，反而简单）

// 构造二叉树
// 106.从中序与后序遍历构造二叉树
// 105.从前序与中序遍历构造二叉树
// 654.最大二叉树：以nums最大值为根节点，前半递归为左子树，右半递归为右子树

#include <algorithm>
#include <deque>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val = 0, TreeNode *left = nullptr, TreeNode *right = nullptr)
        : val(val), left(left), right(right) {}
};

class Solution
{
  public:
    // 前序
    vector<int> preorderTraversal(TreeNode *root)
    {
        vector<int> res;
        stack<TreeNode *> stk;
        if (root) {
            stk.push(root);
        }
        while (!stk.empty()) {
            TreeNode *node = stk.top();
            res.push_back(node->val);
            stk.pop();
            if (node->right) {
                stk.push(node->right);
            }
            if (node->left) {
                stk.push(node->left);
            }
        }
        return res;
    }
    // 后序
    vector<int> postorderTraversal(TreeNode *root)
    {
        vector<int> res;
        stack<TreeNode *> stk;
        if (root) {
            stk.push(root);
        }
        while (!stk.empty()) {
            TreeNode *node = stk.top();
            res.push_back(node->val);
            stk.pop();
            if (node->left) {
                stk.push(node->left);
            }
            if (node->right) {
                stk.push(node->right);
            }
        }
        std::reverse(res.begin(), res.end());
        return res;
    }
    // 中序
    vector<int> inorderTraversal(TreeNode *root)
    {
        vector<int> res;
        stack<TreeNode *> stk;
        TreeNode *cur = root; // 借助指针访问节点
        while (cur || !stk.empty()) {
            while (cur) {
                stk.push(cur);
                cur = cur->left;
            }
            TreeNode *node = stk.top();
            stk.pop();
            res.push_back(node->val);
            cur = node->right; // 指针指向右孩子
        }
        return res;
    }
    // 层序
    vector<vector<int>> levelOrder(TreeNode *root)
    {
        vector<vector<int>> res;
        queue<TreeNode *> que;
        if (root) {
            que.push(root);
        }
        while (!que.empty()) {
            int n = que.size();
            vector<int> layer;
            for (int i = 0; i < n; ++i) {
                TreeNode *node = que.front();
                layer.push_back(node->val);
                que.pop();
                if (node->left) {
                    que.push(node->left);
                }
                if (node->right) {
                    que.push(node->right);
                }
            }
            res.push_back(layer);
        }
        return res;
    }
};

class Solution257
{
  public:
    vector<string> res;
    vector<int> path; // path直接设置成string回溯时很不便
    vector<string> binaryTreePaths(TreeNode *root)
    {
        backtracking(root);
        return res;
    }

    void backtracking(TreeNode *node)
    {
        // 根节点到叶子节点的路径，所以只能前序：根左右
        path.push_back(node->val);
        // 叶子节点
        if (node->left == nullptr && node->right == nullptr) {
            // path转成字符串，存入res
            string sPath;
            if (!path.empty()) {
                for (int i = 0; i < path.size() - 1; ++i) {
                    sPath += std::to_string(path[i]);
                    sPath += "->";
                }
                sPath += std::to_string(path.back());
            }
            res.push_back(sPath);
            return;
        }
        if (node->left) {
            backtracking(node->left);
            path.pop_back();
        }
        if (node->right) {
            backtracking(node->right);
            path.pop_back();
        }
    }
};

class Solution112
{
  public:
    bool hasPathSum(TreeNode *root, int targetSum)
    {
        if (root == nullptr) {
            return false;
        }
        return traversal(root, targetSum - root->val);
    }

    bool traversal(TreeNode *root, int diff) // diff=targetSum与节点之差
    {
        if (root->left == nullptr && root->right == nullptr && diff == 0) {
            return true;
        }
        // 节点值有正有负
        if (root->left == nullptr && root->right == nullptr) {
            return false;
        }
        if (root->left) {
            diff -= root->left->val;
            if (traversal(root->left, diff)) {
                return true;
            }
            diff += root->left->val;
        }
        if (root->right) {
            diff -= root->right->val;
            if (traversal(root->right, diff)) {
                return true;
            }
            diff += root->right->val;
        }
        return false;
    }
};

class Solution113
{
  public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> pathSum(TreeNode *root, int targetSum)
    {
        // 需要记录所有路径，标准回溯
        if (root == nullptr) {
            return {};
        }
        path.push_back(root->val);
        backtracking(root, targetSum - root->val);
        return res;
    }

    void backtracking(TreeNode *root, int diff)
    {
        // 叶子节点，节点值有正有负，因此必须遍历到叶子节点才知道该条路径能不能加入答案
        if (root->left == nullptr && root->right == nullptr) {
            if (diff == 0) {
                res.push_back(path);
            }
            return;
        }
        if (root->left) {
            path.push_back(root->left->val);
            diff -= root->left->val;
            backtracking(root->left, diff);
            diff += root->left->val;
            path.pop_back();
        }
        if (root->right) {
            path.push_back(root->right->val);
            diff -= root->right->val;
            backtracking(root->right, diff);
            diff += root->right->val;
            path.pop_back();
        }
    }
};

class Solution106
{
  public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder)
    {
        if (inorder.empty()) {
            return nullptr;
        }
        return traversal(inorder, postorder, 0, inorder.size(), 0, postorder.size());
    }

    TreeNode *traversal(vector<int> &inorder,
                        vector<int> &postorder,
                        int inorderBegin,
                        int inorderEnd,
                        int postorderBegin,
                        int postorderEnd)
    {
        if (postorderBegin == postorderEnd) {
            return nullptr;
        }
        int rootVal = postorder[postorderEnd - 1];
        TreeNode *root = new TreeNode(rootVal);
        if (postorderEnd - postorderBegin == 1) {
            return root;
        }
        int rootInorderIdx = 0; // for循环寻找中序中root位置
        for (int i = inorderBegin; i < inorderEnd; ++i) {
            if (inorder[i] == rootVal) {
                rootInorderIdx = i;
                break;
            }
        }
        // 递归前记录位置, 左开右闭
        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = rootInorderIdx;
        int rightInorderBegin = rootInorderIdx + 1;
        int rightInorderEnd = inorderEnd;

        int leftPostorderBegin = postorderBegin;
        int leftPostorderEnd = postorderBegin + rootInorderIdx - inorderBegin;
        int rightPostorderBegin = leftPostorderEnd;
        int rightPostorderEnd = postorderEnd - 1;

        root->left = traversal(inorder, postorder, leftInorderBegin, leftInorderEnd, leftPostorderBegin, leftPostorderEnd);
        root->right = traversal(inorder, postorder, rightInorderBegin, rightInorderEnd, rightPostorderBegin, rightPostorderEnd);
        return root;
    }
};